package org.tree;

/**
 * @author: 默苍璃
 * @date: 2023-04-13 08:53
 * <p>
 * 二叉树的基本操作
 */
class BinaryTree<T> {

    private final int maxNodes = 100;

    private Node<T> root;

    /**
     * 创建一棵空二叉树
     */
    public BinaryTree() {
        //创建根结点，该结点的数据域为空
        this.root = new Node<T>();
    }

    /**
     * 创建一棵以数据元素x为根结点的二叉树
     *
     * @param x
     */
    public BinaryTree(T x) {
        //创建一棵以数据元素x为根结点的二叉树
        this.root = new Node<T>(x);
    }


    /**
     * 在当前二叉树的parent结点中插入一个新的左子结点，
     * 若已存在左子树，则将该左子树变成新左子结点的左孩子树
     * <p>
     * <p>
     * 注意，若要执行本操作，则必须先确定插入位置，即parent节点
     *
     * @param x
     * @param parent
     * @return
     */
    public boolean insertLeft(T x, Node<T> parent) {
        if (parent == null) {
            return false;
        }
        //创建一个新结点
        Node<T> p = new Node<T>(x);
        if (parent.lChild == null)
        //将新结点直接设置到父结点的左孩子结点
        {
            parent.lChild = p;
        } else {
            //先将父结点原来的左子树设置为新结点的左子树
            p.lChild = parent.lChild;
            //再将新结点设置到父结点的左孩子结点
            parent.lChild = p;
        }
        return true;
    }


    /*在当前二叉树的parent结点中插入一个新的右孩子结点，
若已存在右子树，则将该右子树变成新右孩子结点的左子树*/
    public boolean insertRight(Node<T> parent) {
        return true;
    }


    /**
     * 删除在当前二叉树的parent结点中的左子树
     *
     * @param parent
     * @return
     */
    public boolean deleteLeft(Node<T> parent) {
        if (parent == null) {
            return false;
        } else {
            parent.lChild = null;
            return true;
        }
    }

    //删除在当前二叉树的parent结点中的右子树
    public boolean deleteRight(Node<T> parent) {
        return true;
    }

    public boolean search(T x) {
        return true;
    } //在当前二叉树中查找数据x

    public void traversal(int i) {
    }  //按某种方式遍历当前二叉树的全部结点


    /**
     * 求当前二叉树的高度
     * <p>
     * 使用后序遍历法计算二叉树的高度
     * 当parent为root时，即可计算当前二叉树的高度
     *
     * @param parent
     * @return
     */
    public int getHeight(Node<T> parent) {
        int lh, rh, max;
        if (parent != null) {
            //求左子树的高度
            lh = getHeight(parent.lChild);
            //求右子树的高度
            rh = getHeight(parent.rChild);
            max = lh > rh ? lh : rh;
            return max + 1;
        } else {
            return 0;
        }
    }


    /**
     * 先序遍历二叉树的递归算法
     *
     * @param node
     */
    public void preorder(Node<T> node) {
        if (node == null) {
            return;
        } else {
            System.out.println(node.data);
            //先序遍历左子树
            preorder(node.lChild);
            //先序遍历右子树
            preorder(node.rChild);
        }
    }


    /**
     * 中序遍历二叉树的递归算法
     *
     * @param node
     */
    public void inorder(Node<T> node) {
        if (node == null) {
            return;
        } else {
            //中序遍历左子树
            inorder(node.lChild);
            //访问根结点
            System.out.println(node.data);
            //中序遍历右子树
            inorder(node.rChild);
        }
    }

    /**
     * 后序遍历二叉树的递归算
     *
     * @param node
     */
    public void postorder(Node<T> node) {
        if (node == null) {
            return;
        } else {
            //后序遍历左子树
            postorder(node.lChild);
            //后序遍历右子树
            postorder(node.rChild);
            //访问根结点
            System.out.println(node.data);
        }
    }

    public void levelOrder() {
        //构造一个队列
        Node<T>[] queue = new Node[this.maxNodes];
        //队首指针、队尾指针
        int front, rear;
        if (this.root == null) {
            return;
        }
        //队列暂时为空，队首指针不指向任何一个数组元素
        front = -1;
        //队列暂时为空，队尾指针指向第一个数组元素
        rear = 0;
        //二叉树的根结点进队列
        queue[rear] = this.root;
        while (front != rear) {
            front++;
            //访问队首结点的数据域
            System.out.println(queue[front].data);
            /*将队首结点的左孩子结点进队列*/
            if (queue[front].lChild != null) {
                rear++;
                queue[rear] = queue[front].lChild;
            }
            /*将队首结点的右孩子结点进队列*/
            if (queue[front].rChild != null) {
                rear++;
                queue[rear] = queue[front].rChild;
            }
        }
    }


}
